﻿//-----------------------------------------------------------------------------
// 文 件 名: 150_逆波兰表达式求值.cpp
// 作    者：adoredee
// 创建时间：2019.08.19
// 描    述：逆波兰表达式求值
// 版    本：
//-----------------------------------------------------------------------------
// Copyright (C) 2019 Shanghai Jiao Tong University
//-----------------------------------------------------------------------------


/*
	根据逆波兰表示法，求表达式的值。

	有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

	说明：
	整数除法只保留整数部分。
	给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

	示例 1：
	输入: ["2", "1", "+", "3", "*"]
	输出: 9
	解释: ((2 + 1) * 3) = 9

	示例 2：
	输入: ["4", "13", "5", "/", "+"]
	输出: 6
	解释: (4 + (13 / 5)) = 6

	示例 3：
	输入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
	输出: 22
	解释:
	((10 * (6 / ((9 + 3) * -11))) + 17) + 5
	= ((10 * (6 / (12 * -11))) + 17) + 5
	= ((10 * (6 / -132)) + 17) + 5
	= ((10 * 0) + 17) + 5
	= (0 + 17) + 5
	= 17 + 5
	= 22
*/

#include <iostream>
#include <vector>
#include <stack>
#include <string>

using namespace std;

int evalRPN(vector<string>& tokens)
{
	// 将string字符串转换为int类型

	/*
	atoi()和stoi()函数的区别
	1. stoi函数只能将字符串转换为十进制，会对字符串进行检查，如果超过范围，会报错，遇到非法字符同样会停下来，不会报错；
	默认要求输入的参数字符串是符合int范围的[-2147483648, 2147483647]，否则会runtime error。
	2. atoi函数只能将字符串转换为十进制，则不做范围检查，若超过int范围[-2147483648, 2147483647]，
	则显示-2147483648（溢出下界）或者2147483647（溢出上界）。

	stoi头文件：<string>,c++函数
	atoi头文件:<cstdlib>,c函数
	atoi()的参数是 const char* ,因此对于一个字符串str我们必须调用 c_str()的方法把这个string转换成 const char*类型的,
	而stoi()的参数是const string*,不需要转化为 const char*；
	*/

	// .c_str()函数返回一个指向正规C字符串的指针常量
	// 以下三个都正确
	stack<int> st;

	for (size_t i = 0; i < tokens.size(); ++i)
	{
		if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/")
		{
			int nB = st.top();
			st.pop();
			int nA = st.top();
			st.pop();
			if (tokens[i] == "+")
				st.push(nA + nB);
			else if (tokens[i] == "-")
				st.push(nA - nB);
			else if (tokens[i] == "*")
				st.push(nA * nB);
			else if (tokens[i] == "/")
				st.push(nA / nB);
		}
		else
		{
			st.push(atoi(tokens[i].c_str()));
		}
	}

	return st.top();
}

int main()
{   
	vector<string> pStr = { "10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+" };

	int nSum = evalRPN(pStr);
	
	cout << "该逆波兰表达式的值为：" << nSum << endl;

	return 0;
}